package com.datastructures2.graph.最短路径;


import com.datastructures2.graph.有向图.EdgeWeightedDirectedCycle;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdOut;

/**
 * 基于队列的Bellman-Ford算法
 * 在任意含有V个顶点的加权有向图中给定起点s，从s无法到达任何负权重环
 * 将distTo[s]初始化为0，其他distTo[]元素为无穷大，以任意顺序放松有向图的所有边，重复V轮
 * @author MaoLin Wang
 * @date 2020/2/2421:41
 */
public class BellmanFordSP {

    private double[] distTo;
    private DirectedEdge[] edgeTo;

    /**
     * 该顶点是否在队列中
     */
    private boolean[] onQ;
    /**
     * 正在被放松的顶点
     */
    private Queue<Integer> queue;

    /**
     * relax()的调用次数
     */
    private int cost;

    /**
     * edgeTo[]中是否有负权重环
     */
    private Iterable<DirectedEdge> cycle;

    public BellmanFordSP(EdgeWeightedDigraph digraph,int s) {
        distTo=new double[digraph.V()];
        edgeTo=new DirectedEdge[digraph.V()];
        onQ=new boolean[digraph.V()];
        queue=new Queue<>();

        for (int v = 0; v < digraph.V(); v++) {
            distTo[v]=Double.POSITIVE_INFINITY;
        }
        distTo[s]=0.0;
        queue.enqueue(s);
        onQ[s]=true;

        while (!queue.isEmpty() && !hasNegativeCycle()){
            int v=queue.dequeue();
            onQ[v]=false;
            relax(digraph,v);
        }
    }

    private void relax(EdgeWeightedDigraph digraph, int v) {
        for (DirectedEdge edge:digraph.adj(v)){
            int to=edge.to();
            if (distTo[to]>distTo[v]+edge.weight()){
                distTo[to]=distTo[v]+edge.weight();
                edgeTo[to]=edge;
                if (!onQ[to]){
                    queue.enqueue(to);
                    onQ[to]=true;
                }
            }
            //调用V次relax后查找负权重环
            if (cost++ % digraph.V()==0){
                findNegativeCycle();
            }
        }
    }

    /**
     * 查找负权重环，没有则返回null
     */
    private void findNegativeCycle() {
        int V=edgeTo.length;
        EdgeWeightedDigraph digraph;
        digraph=new EdgeWeightedDigraph(V);
        for (int v = 0; v < V; v++) {
            if (edgeTo[v]!=null){
                digraph.addEdge(edgeTo[v]);
            }
        }
        EdgeWeightedDirectedCycle directedCycle;
        directedCycle=new EdgeWeightedDirectedCycle(digraph);
        cycle=directedCycle.cycle();

    }

    /**
     * 是否含有负权重环
     * @return
     */
    public boolean hasNegativeCycle() {
        return cycle!=null;
    }

    public Iterable<DirectedEdge> negativeCycle(){
        return cycle;
    }
    public boolean hasPathTo(int v){
        return distTo[v]<Double.POSITIVE_INFINITY;
    }
    public double distTo(int v){
        return distTo[v];
    }
    public Iterable<DirectedEdge> pathTo(int v){
        if (hasNegativeCycle())
            throw new UnsupportedOperationException("Negative cost cycle exists");
        if (!hasPathTo(v)) return null;
        Stack<DirectedEdge> path = new Stack<DirectedEdge>();
        for (DirectedEdge e = edgeTo[v]; e != null; e = edgeTo[e.from()]) {
            path.push(e);
        }
        return path;
    }

    public static void main(String[] args) {
        In in = new In(args[0]);
        int s = Integer.parseInt(args[1]);
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(in);

        BellmanFordSP sp = new BellmanFordSP(G, s);

        // print negative cycle
        if (sp.hasNegativeCycle()) {
            for (DirectedEdge e : sp.negativeCycle())
                StdOut.println(e);
        }

        // print shortest paths
        else {
            for (int v = 0; v < G.V(); v++) {
                if (sp.hasPathTo(v)) {
                    StdOut.printf("%d to %d (%5.2f)  ", s, v, sp.distTo(v));
                    for (DirectedEdge e : sp.pathTo(v)) {
                        StdOut.print(e + "   ");
                    }
                    StdOut.println();
                }
                else {
                    StdOut.printf("%d to %d           no path\n", s, v);
                }
            }
        }

    }
}
